package 链表;

import java.util.HashMap;
import java.util.Map;
//https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId=295&tqId=663&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
public class BM16_删除有序链表中重复的元素II {

	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(2);
		node1.next = node2;
		node2.next = node3;
		BM16_删除有序链表中重复的元素II test = new BM16_删除有序链表中重复的元素II();
		System.out.println(test.deleteDuplicates(node1));
	}

	/*
	 * 具体做法：
		    step 1：给链表前加上表头，方便可能的话删除第一个节点。
				ListNode res = new ListNode(0);
				//在链表前加一个表头
				res.next = head; 
			step 2：遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。
			step 3：在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
			step 4：返回时去掉添加的表头。
	 */
	public ListNode deleteDuplicates (ListNode head) {
		if(head == null) return head;
		ListNode pre = new ListNode(-1);
		pre.next = head;
		ListNode curr = pre;
		while(curr.next != null && curr.next.next != null) {
			//遇到相邻两个节点值相同
			if(curr.next.val == curr.next.next.val) {
				int temp = curr.next.val;
				 //将所有相同的都跳过
				while(curr.next != null && curr.next.val == temp) {
					curr.next = curr.next.next;
				}
			}else {
				curr = curr.next;
			}
		}
		//返回时去掉表头
		return pre.next;
    }
	
	/**
	 * 具体做法：
		step 1：遍历一次链表用哈希表记录每个节点值出现的次数。
		step 2：在链表前加一个节点值为0的表头，方便可能的话删除表头元素。
		step 3：再次遍历该链表，对于每个节点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。
		step 4：返回时去掉增加的表头。
	 */
	public ListNode deleteDuplicates01(ListNode head) {
        //空链表
        if(head == null) return null;
        Map<Integer,Integer> mp = new HashMap<>();
        ListNode cur = head;
        //遍历链表统计每个节点值出现的次数
        while(cur != null){
            if(mp.containsKey(cur.val))
                mp.put(cur.val, (int)mp.get(cur.val) + 1);
            else
                mp.put(cur.val,1);
            cur = cur.next;
        }
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head;
        cur = res;
        //再次遍历链表
        while(cur.next != null){
            //如果节点值计数不为1
            if(mp.get(cur.next.val) != 1)
                //删去该节点
                cur.next = cur.next.next;
            else
                cur = cur.next;
        }
        //去掉表头
        return res.next;
    }
}
